package leetcode.all;

import datastruct.list.ListNode;

public class Solution92 {

    /**
     * 思路：先找到left的前一个结点pre，然后把left到right的节点依次头插到pre后面
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //虚拟一个头节点dum
        ListNode dum = new ListNode();
        dum.next = head;
        //cur指向当前节点，pre指向前一个结点，count表示cur指向第几个节点
        ListNode pre = dum;
        ListNode cur = head;
        int count = 1;
        //往后找，直到cur指向第left个节点，pre指向第left-1个节点
        while (count<left){
            pre = pre.next;
            cur = cur.next;
            count++;
        }
        //此时cur指向left，pre指向left-1，对pre后面left到right节点进行头插
        ListNode leftNode = cur; //逆序后leftNode的next指向right+1个节点
        pre.next = null;         //把头插的头节点pre和后面断开
        ListNode next = null;    //用于暂存cur的下一个节点
        while (count<=right){
            next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = next;
            count++;
        }
        //leftNode和right+1接上，此时cur指向right+1
        leftNode.next = cur;
        return dum.next;
    }
}
